package com.rayboo.example.algorithm.sort;

import com.rayboo.example.util.ArrayUtils;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author ray
 * @since 2019/08/01
 *
 * <p>归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
 *
 * <p>https://cloud.tencent.com/developer/article/1465640
 */
public class MergeSort {

    public static void main(String[] args) {
        int arr[] = ArrayUtils.randomRepeatIntArray(0, 100, 10);
        System.out.println("排序前：\n" + Arrays.toString(arr));

        arr = new MergeSort().sort(arr);
        System.out.println("排序后：\n" + Arrays.toString(arr));
    }

    /**
     * 排序
     *
     * @param sourceArray 源数组
     * @return 排序后的数组
     */
    public int[] sort(int[] sourceArray) {
        for (int gap = 1; gap < sourceArray.length; gap = 2 * gap) {
            mergeSort(sourceArray, gap, sourceArray.length);
        }
        return sourceArray;
    }

    /**
     * 归并排序
     *
     * @param arr    数组
     * @param gap    步长
     * @param length 长度
     */
    private void mergeSort(int[] arr, int gap, int length) {
        int i = 0;

        // 归并gap长度的两个相邻子表
        for (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap) {
            merge(arr, i, i + gap - 1, i + 2 * gap - 1);
        }

        // 余下两个子表，后者长度小于gap
        if (i + gap - 1 < length) {
            merge(arr, i, i + gap - 1, length - 1);
        }
    }

    /**
     * 调整
     *
     * @param arr  数组
     * @param low  第一段序列的下标
     * @param mid  第二段序列的下标
     * @param high 最大长度
     */
    private void merge(int[] arr, int low, int mid, int high) {
        int[] tempArr;
        int i = low, j = mid + 1, k = 0;
        tempArr = Arrays.copyOf(arr, high - low + 1);

        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (arr[i] < arr[j]) {
                tempArr[k++] = arr[i++];
            } else {
                tempArr[k++] = arr[j++];
            }
        }

        // 把左边剩余的数移入数组
        while (i <= mid) {
            tempArr[k++] = arr[i++];
        }

        // 把右边边剩余的数移入数组
        while (j <= high) {
            tempArr[k++] = arr[j++];
        }

        // 把新数组中的数据覆盖temp数组
        System.arraycopy(tempArr, 0, arr, low, tempArr.length);
    }
}
